All Questions
14 questions
3votes
1answer
136views
How well can shortest common supersequence over small alphabet size be approximated?
Given a list $L$ of sequences of the first $n+1$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $L$? The paper here shows that if $n$ is not ...
- 219
0votes
0answers
55views
Multi-dimensional 0-1 Knapsack problem with a high number of dimensions
I would like to solve a multi-dimensional 0-1 Knapsack problem, by looking for approximation algorithms with constant approximation ratio if possible. Here the particularity is that the number of ...
- 113
2votes
1answer
222views
Maximize a special monotone submodular function - is it easier?
I am looking for a way to optimize the function $f$, defined below. First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
- 649
1vote
0answers
79views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
user53330
2votes
1answer
140views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
user53330
4votes
1answer
398views
The complexity of decomposing a bi-stochastic matrix
A bistochastic matrix $A$ is a matrix with positive entries in which each row/column sums to $1$. By the Birkhoff von-Neumann theorem $A$ is a convex combination of permutation matrices. Further, by ...
- 1,224
0votes
0answers
136views
Maximize number of bins and minimize cost of elements chosen from a set
I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
- 101
1vote
1answer
109views
Approximations for the Stable Fixtures Problem
I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at ...
- 113
2votes
0answers
242views
Recent insights on algorithms for 1D bin packing
This is just a general question on recent algorithms for the 1D bin packing problem. I just want to collect some information on this issue, so I’m grateful for any information. Especially heuristics ...
- 121
12votes
2answers
4kviews
Find all pairs of values that are close under Hamming distance
I have a few million 32-bit values. For each value, I want to find all other values within a hamming distance of 5. In the naive approach, this requires $O(N^2)$ comparisons, which I want to avoid. ...
- 223
2votes
0answers
99views
Optimal additive basis for decomposing/partitioning an integer as a sum of two integers
I'm going to be given a positive integer $z$, and I want to find an optimal basis $B$ that is good for $z$. A basis $B$ is a multiset of positive integers. The basis $B$ is considered good for $z$ ...
- 12.5k
6votes
0answers
416views
Bipartite vertex separator
Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph? I have a ...
- 211
8votes
1answer
594views
Approximation algorithms for Directed Minimum Cut with Cardinality Constraints
We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
- 263
2votes
1answer
368views
Finding largest closest subsets
Original question: Base problem: Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose subsets $s_i$ ($i=1,...,N$) from $A$. Elements cannot be repeated within ...
